home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
C/C++ Users Group Library 1996 July
/
C-C++ Users Group Library July 1996.iso
/
listings
/
v_12_10
/
allison
/
xref.c
< prev
next >
Wrap
C/C++ Source or Header
|
1994-09-06
|
3KB
|
148 lines
LISTING 7
/* xref.c: Prints line numbers where each word occurs */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define WORD_WIDTH 15
/* Node structure for each list of line numbers */
struct List
{
int lnum;
struct List *next;
};
typedef struct List List;
/* Node structure for tree of distinct words */
struct Tree
{
char word[WORD_WIDTH];
List *lstptr;
struct Tree *left,*right;
};
typedef struct Tree Tree;
/* Tree and list functions */
Tree *addword(Tree *, char *);
List *addline(List *, int);
Tree *find_node(Tree *, char *);
void print_tree(Tree *t);
void print_list(List *);
int ndistinct = 0;
main(int argc, char *argv[])
{
char linebuf[BUFSIZ];
Tree *words = NULL;
int lineno = 0;
/* Do optional input redirection */
if (argc > 1)
assert(freopen(argv[1],"r",stdin));
/* Process each line of text file */
while (fgets(linebuf,BUFSIZ,stdin) != NULL)
{
char *wordptr, *lineptr = linebuf;
char *bad_chars = " \t\n\f\v\\\"~!@#$%^&*()+'"
"|`1234567890-=\{}[]:;<>?,./";
++lineno;
/* Process each word in line */
while ((wordptr = strtok(lineptr,bad_chars)) != NULL)
{
Tree *node;
words = addword(words,wordptr);
node = find_node(words,wordptr);
node->lstptr = addline(node->lstptr,lineno);
lineptr = NULL;
}
}
/* Print results */
printf("No. of distinct words: %d\n\n",ndistinct);
print_tree(words);
return 0;
}
Tree *addword(Tree *tp, char *word)
{
if (tp == NULL)
{
/* Add new entry */
++ndistinct;
tp = malloc(sizeof(Tree));
strncpy(tp->word,word,WORD_WIDTH)[WORD_WIDTH] = '\0';
tp->left = tp->right = NULL;
tp->lstptr = NULL;
}
else if (strcmp(tp->word,word) < 0)
tp->right = addword(tp->right,word);
else if (strcmp(tp->word,word) > 0)
tp->left = addword(tp->left,word);
return tp;
}
List *addline(List *lp, int n)
{
if (lp == NULL)
{
/* Append new line number to list */
List *newp = malloc(sizeof(List));
assert(newp);
newp->lnum = n;
newp->next = NULL;
return newp;
}
else if (lp->lnum != n)
lp->next = addline(lp->next,n);
return lp;
}
void print_tree(Tree *tp)
{
if (tp != NULL)
{
/* Inorder traversal */
print_tree(tp->left);
printf("%-*.*s: ",WORD_WIDTH,WORD_WIDTH,tp->word);
print_list(tp->lstptr); putchar('\n');
print_tree(tp->right);
}
}
void print_list(List *lp)
{
const int NUM_WIDTH = 5;
const int INDENT = WORD_WIDTH + 2;
const int NUMS_PER_LINE = 8;
int count;
for (count = 0; lp != NULL; lp = lp->next, ++count)
{
printf("%*d",NUM_WIDTH,lp->lnum);
if ((count+1) % NUMS_PER_LINE == 0
&& lp->next != NULL)
printf("\n%*c",INDENT,' ');
}
}
Tree *find_node(Tree *tp, char *s)
{
/* Binary search for word */
if (strcmp(tp->word,s) > 0)
return find_node(tp->left,s);
else if (strcmp(tp->word,s) < 0)
return find_node(tp->right,s);
else
return tp;
}